package algorithm.tree;

/**
 * 红黑树
 *
 * (1) 每个节点或者是黑色，或者是红色。
 * (2) 根节点是黑色。
 * (3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！] 注意：叶子节点，是只为空(NIL或null)的节点。
 * (4) 如果一个节点是红色的，则它的子节点必须是黑色的。
 * (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。注意：确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。
 *
 *
 * @author: fengpeng
 * @date: 2019/1/23  下午5:00
 */
public class RedBlackTree<T extends Comparable<? super T>> {

    /**
     * 对x节点进行左旋转
     * 即将x节点变成其右孩子节点的左孩子且原右孩子节点的左孩子成为x节点的右孩子（x节点的左孩子不变），原右孩子节点的右孩子不变
     *       x                      y
     *     /   \                 /    \
     *   a     y              x        c
     *       /   \           /  \
     *     b      c       a      b
     *
     * @param x 待旋转的节点
     */
    private void leftRotate(RedBlackNode<T> x){
        //获取x的右孩子
        RedBlackNode<T> xRight = x.right;
        //将xRight的左孩子作为x的右孩子
        x.right = xRight.left;
        if (xRight.left != null){
            xRight.left.parent = x;
        }
        //x节点的父节点作为xRight的父节点
        xRight.parent = x.parent;


    }

}
